template <typename T, typename U>
class TreapMap
{
	struct TNode
	{
		TNode(const T &k): key(k), priority(rand()), lchild(0), rchild(0) {}
		TNode(const T &k, const U &v): key(k), val(v), priority(rand()), lchild(0), rchild(0) {}
		TNode *lchild;
		TNode *rchild;
		T key;
		U val;
		unsigned int priority;
	};

public:
	TreapMap()
	{
		root = NULL;
		srand(time(0));
	}

	~TreapMap()
	{
		clear();
	}

	bool insert(const T &key, const U &val)
	{
		TNode *tmp;
		bool r = insertAt(root, key, tmp);
		tmp->val = val;
		return r;
	}

	U& operator[](const T &key)
	{
		TNode *tmp;
		insertAt(root, key, tmp);
		return tmp->val;
	}

	bool contain(const T &key)
	{
		TNode *nd = getAt(root, key);
		return nd != NULL;
	}

	// if key exists then return true and the val will be assigned, otherwise return false
	bool tryGet(const T &key, U &val)
	{
		TNode *nd = getAt(root, key);
		if (nd != NULL)
		{
			val = nd->val;
			return true;
		}
		return false;
	}

	// if key exists then return true and the val will be modified, otherwise return false
	bool tryUpdate(const T &key, const U &val)
	{
		TNode *nd = getAt(root, key);
		if (nd != NULL)
		{
			nd->val = val;
			return true;
		}
		return false;
	}

	// if key doesn't exist return false
	bool remove(const T &key)
	{
		TNode *&nd = getAt(root, key);
		if (nd == NULL)
			return false;
		removeAt(nd);
		cnt--;
		return true;
	}

	void clear()
	{
		destroy(root);
		root = NULL;
		cnt = 0;
	}

	unsigned int size() const
	{
		return cnt;
	}

private:
	// if key has existed then return false otherwise return true
	// nd is the node whose KEY is key
	bool insertAt(TNode *&tree, const T &key, TNode *&nd)
	{
		if (tree == NULL)
		{
			tree = new TNode(key);
			nd = tree;
			cnt++;
			return true;
		}
		if (key == tree->key)
		{
			nd = tree;
			return false;
		}
		else if (key < tree->key)
		{
			bool r = insertAt(tree->lchild, key, nd);
			if (tree->lchild->priority > tree->priority)
				rotate_right(tree);
			return r;
		}
		else
		{
			bool r = insertAt(tree->rchild, key, nd);
			if (tree->rchild->priority > tree->priority)
				rotate_left(tree);
			return r;
		}
	}

	TNode *&getAt(TNode *&tree, const T &key)
	{
		if (tree == NULL)
			return tree;
		if (key == tree->key)
			return tree;
		else if (key < tree->key)
			return getAt(tree->lchild, key);
		else
			return getAt(tree->rchild, key);
	}

	void removeAt(TNode *&tree)
	{
		TNode *maxp = NULL;
		unsigned int p = 0;
		if (tree->lchild)
		{
			maxp = tree->lchild;
			p = tree->lchild->priority;
		}
		if (tree->rchild && tree->rchild->priority >= p)
			maxp = tree->rchild;
		if (maxp == NULL)
		{
			delete tree;
			tree = NULL;
		}
		else if (maxp == tree->lchild)
		{
			rotate_right(tree);
			removeAt(tree->rchild);
		}
		else
		{
			rotate_left(tree);
			removeAt(tree->lchild);
		}
	}

	void rotate_left(TNode *&tree)
	{
		TNode *rc = tree->rchild;
		tree->rchild = rc->lchild;
		rc->lchild = tree;
		tree = rc;
	}

	void rotate_right(TNode *&tree)
	{
		TNode *lc = tree->lchild;
		tree->lchild = lc->rchild;
		lc->rchild = tree;
		tree = lc;
	}

	void destroy(TNode *tree)
	{
		if (tree)
		{
			destroy(tree->lchild);
			destroy(tree->rchild);
			delete tree;
		}
	}

private:
	TNode *root;
	unsigned int cnt;
};